// 邻接表，表示图
// 对于有向图，有入度（in-degree）和出度（out-degree）入度是指指向该节点的边的数量，出度是指从该节点出发指向其他节点的边的数量。
// 顶点 表节点
class Vertex {
  /**
   * @description:
   * @param {*} data记录顶点节点的数值
   * @return {*}
   */
  constructor(data) {
    this.data = data; // 顶点域
    this.firstEdge = null; // 指向第一个邻接边的指针，指向当前顶点的边表中的第一个节点
    this.outNum = 0; // 在无向图中表示与顶点邻接的边的数量，在有向图中为出度
    this.inNum = 0; // 在有向图中为顶点的入度
  }
}
// 边 表节点
class Edge {
  constructor(data, weight = 0, nextEdge = null) {
    this.data = data; // 邻接点域
    this.nextEdge = nextEdge; // 指向下一条邻接边
    this.weight = weight; // 权重
  }
}

// 创建图
class Graph {
  constructor(isDirect) {
    this.eNum = 0; // 边的数目
    this.adj = []; // 顶点表
    this.isDirect = isDirect; // 是否是有向图
  }
  // 初始化顶点表
  initVertex(verArr) {
    for (let i = 0; i < verArr.length; i++) {
      let newVer = new Vertex(verArr[i]);
      this.adj[i] = newVer;
    }
  }

  // 插入新的顶点
  insertVertex(x) {
    // 创建新顶点
    let newVer = new Vertex(x);
    // 添加到当前的顶点表
    this.adj.push(newVer);
  }

  // 找到节点x在adj中所在的位置
  // 前面加上下划线表示不应该在具体实例中调用该方法
  _find(x) {
    let pos = -1;

    for (let i = 0; i < this.adj.length; i++) {
      if (x == this.adj[i].data) pos = i;
    }

    return pos;
  }

  // 判断图中是否存在边(x,y)或者<x, y>。
  //从顶点x的边表第一元素开始遍历，如果发现存在y节点则说明顶点x和顶点y之间已经有了一条边
  hasEdge(x, y) {
    let pos = this._find(x);
    if (pos > -1) {
      // 找出顶点的第一条边
      let curVer = this.adj[pos].firstEdge;

      if (!curVer) {
        // 没有与顶点x的邻接点
        return false;
      } else {
        // 至少有一个节点与顶点x是相邻的
        // 遍历顶点的所有邻接节点
        while (curVer) {
          // 如果相等，说明存在边
          if (curVer.data === y) return true;

          curVer = curVer.nextEdge;
        }

        return false;
      }
    }
  }

  // 向图中插入边(x, y)或者边<x, y>
  /**
   1.连接任意顶点，分为有向图还是无向图，
    如果是无向图的话，在插入边(x, y)后还要再插入边(y, x)，因为用邻接表来存储无向图时，顶点x的边表中具有顶点y，那么顶点y的边表中必然也有顶点x。
    如果是有向图中的话，只需要插入边<x, y>就可以
   2.在插入边的时候，首先判断下顶点x和顶点y之间是否已经存在了一条边了，只有x和y之间没有边时，才可以在顶点x和顶点y之间插入一条边
   3.在插入边的过程中，如果是有向图时，同时更新每个顶点的入度和出度，而如果是无向图的话，则分别更新了与x和y相邻的节点的数量。
   */
  addEdge(x, y, w = 0) {
    let posX = this._find(x);
    let posY = this._find(y);
    let newEdgeX = new Edge(x, w);
    let newEdgeY = new Edge(y, w);
    // 如果是无向图，在插入边(x, y)时还要插入边(y, x)
    if (!this.isDirect) {
      // <x, y>或者<y, x>边不存在
      if (!this.hasEdge(x, y) && !this.hasEdge(y, x)) {
        // 如果顶点x在顶点表中
        if (posX > -1) {
          // 取出顶点x的第一条边
          let curVer = this.adj[posX].firstEdge;
          // 如果第一条边不存在
          if (!curVer) {
            // 创建第一条边
            this.adj[posX].firstEdge = newEdgeY;
            // outNum无向图中，表示顶点邻接边的数量
            this.adj[posX].outNum++;
          } else {
            let len = this.adj[posX].outNum - 1;
            // x点的邻接边存在，往所有边之后追加边
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeY;
            // 邻接边数量+1
            this.adj[posX].outNum++;
          }
        }
        // 如果顶点y在顶点表中
        if (posY > -1) {
          // 取出顶点y的第一条边
          let curVer = this.adj[posY].firstEdge;
          if (!curVer) {
            this.adj[posY].firstEdge = newEdgeX;
            this.adj[posY].outNum++;
          } else {
            let len = this.adj[posY].outNum - 1;
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeX;
            this.adj[posY].outNum++;
          }
        }
        // 边的数量+1
        this.eNum++;
      }
    }
    // 有向图， 只用处理<x, y>方向的边
    else {
      if (!this.hasEdge(x, y)) {
        // 如果顶点x在顶点表中
        if (posX > -1) {
          // x顶点的第一条边
          let curVer = this.adj[posX].firstEdge;
          // 如果当前顶点没有第一个边节点
          if (!curVer) {
            this.adj[posX].firstEdge = newEdgeY;
            // x顶点的出度+1
            this.adj[posX].outNum++;
          } else {
            let len = this.adj[posX].outNum - 1;
            while (len--) {
              curVer = curVer.nextEdge;
            }
            curVer.nextEdge = newEdgeY;
            // 顶点x的出度+1
            this.adj[posX].outNum++;
          }
        }
        // 如果顶点x在顶点表中
        if (posY > -1) {
          let curVer = this.adj[posY];
          // 顶点y的入度增长
          curVer.inNum++;
        }
      }
    }
  }

  // 在图中删除边(x, y)或者边<x, y>
  // 在无向图中删除边(x, y)时，同时也需要删除(y, x)，有向图则只需要删除边<x, y>就可以
  // 由于是由邻接表表示的数据结构，当删除边(x, y)时也需要同时删除边(y, x);
  removeEdge(x, y) {
    //在图中删除边(x, y)
    if (this.hasEdge(x, y)) {
      let posX = this._find(x); //查找x顶点
      let posY = this._find(y); //查找y顶点
      let curVerX = this.adj[posX].firstEdge; // x的第一条边
      let curVerY = this.adj[posY].firstEdge; //y的第一条边
      // 首先是无向图，当删除边(x, y)时也需要同时删除边(y, x)
      if (!this.isDirect) {
        // 删除边(x, y)
        // 如果顶点的第一个节点即是要找的节点
        if (curVerX.data === y) {
          // 删除第一条边，把顶点x的nextEdge作为第一条边
          this.adj[posX].firstEdge = curVerX.nextEdge;
          this.adj[posX].outNum--;
          curVerX = null;
        }
        // curVerX如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerX) {
          let preVerX = curVerX;
          // 继续查找下一条边
          curVerX = curVerX.nextEdge;
          if (curVerX && curVerX.data === y) {
            preVerX.nextEdge = curVerX.nextEdge;
            this.adj[posX].outNum--;
            curVerX = null;
          }
        }
        // 删除边(y, x)
        // 如果顶点的第一个节点即是要找的节点
        if (curVerY.data === x) {
          // 把y顶点的下一条边赋值给第一条边
          this.adj[posY].firstEdge = curVerY.nextEdge;
          this.adj[posY].outNum--;
          curVerY = null;
        }
        //curVerY如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerY) {
          let preVerY = curVerY;
          curVerY = curVerY.nextEdge;
          if (curVerY && curVerY.data === x) {
            preVerY.nextEdge = curVerY.nextEdge;
            this.adj[posY].outNum--;
            curVerY = null;
          }
        }
      } else {
        // 删除边<x, y>
        // 如果顶点的第一个节点即是要找的节点
        if (curVerX.data === y) {
          this.adj[posX].firstEdge = curVerX.nextEdge;
          this.adj[posX].outNum--;
          curVerX = null;
        }
        // curVerX如果存在，说明要找的节点不是顶点的第一个节点
        while (curVerX) {
          let preVerX = curVerX;
          curVerX = curVerX.nextEdge;

          if (curVerx && curVerX.data === y) {
            preVerX.nextEdge = curVerX.nextEdge;
            this.adj[posX].outNum--;
            curVerX = null;
          }
        }
        this.adj[posY].inNum--;
      }
      this.eNum--;
    }
  }

  // 从图中删除顶点x,与删除边操作不同
  //在删除图中的一个顶点时，与此顶点所有相邻的边都要删除。
  //   两步操作，第一步删除所有以x为起点的边，第二步删除所有以x为终点的边
  deleteVertex(x) {
    let pos = this._find(x);
    if (pos > -1) {
      // 删除从x出发的边
      let curVer = this.adj[pos].firstEdge;
      while (curVer) {
        this.removeEdge(x, curVer.data);
        curVer = curVer.nextEdge;
      }
      // 删除终点是x的边
      for (let i = 0; i < this.adj.length; i++) {
        let temVer = this.adj[i].firstEdge;

        while (temVer) {
          if (temVer.data === x) {
            this.removeEdge(this.adj[i].data, temVer.data);
          }
          temVer = temVer.nextEdge;
        }
      }
      // 删除顶点x
      this.adj.splice(pos, 1);
    }
  }

  // 与顶点x邻接的所有节点
  //   不断的遍历每个顶点的边
  allNeightbors(x) {
    let pos = this._find(x);

    if (pos > -1) {
      let result = `${x}`;
      let curVer = this.adj[pos].firstEdge;

      while (curVer) {
        result += `=>${curVer.data}`;
        curVer = curVer.nextEdge;
      }

      console.log(result);
    }
  }
}

let arr = ["A", "B", "C", "D", "E"];
let myGraph = new Graph(0);
myGraph.initVertex(arr);
myGraph.addEdge("A", "B");
myGraph.addEdge("A", "C");
myGraph.addEdge("A", "E");
myGraph.addEdge("B", "E");
myGraph.addEdge("C", "E");
myGraph.addEdge("D", "B");
myGraph.addEdge("D", "C");
myGraph.addEdge("D", "E");
for (let i = 0; i < arr.length; i++) {
  myGraph.allNeightbors(arr[i]);
}
// 断开c和、e的连接
myGraph.removeEdge("C", "E");
for (let i = 0; i < arr.length; i++) {
  myGraph.allNeightbors(arr[i]);
}
